So, this is practically one of the core pieces of the final model theory, the set of your
freys research
If duplicator wins the M-round rather in a wet-free sea game between two structures,
for example the one with a length of 20 instead of 10 in five rounds, I guess.
So then A and A are parallel, M equivalent to B and B parallel.
That's another term they missed in the last hour.
Let's write it down here somewhere.
So two such structures with vectors of the same length are M equivalent.
Exactly when for all formulas Φ, which consume in two directions somewhat limited resources,
the quantum rank of Φ is at most M, the quantum rank is the
same as the quantum rank of Φ.
So the quantum rank of Φ is M, and Φ must be built in such a way that these vectors are sufficient for the interpretation of variables.
The joke with these vectors is that they replace the surroundings.
So I assume that I have listed variables X1 to Xn, and if I have a vector of values a1 to a n, then these are the listed values of variables a1 to xn.
So if I still assume that Φ only uses these prescribed variables X1 to Xn, then it is A comma A square that fulfills Φ.
Φ is fulfilled when B comma B square is fulfilled, where we take an environment that always interprets variables Xe by the Ith input of the vector.
So in other words, if a duplicator is able to do M rounds, then the two structures are indistinguishable by formulas of quantum rank, the depth of the quantum rank, at most M.
It is quite intuitive. Every new quantum that I insert, introduces a new element, and that is exactly what happens in this game, that I always attach a new element.
The existence of winning strategies is something that is happening to me. Spoiler is always an all-quantum, and a duplicator is an all-quantum.
The popularity of games in logic is only due to the fact that they give you the possibility to write down quantum that is encoded without actually writing them all down.
What do I need to know to see that I put my opponent in three quants in the chess? I need to see that there is a quantum that I can make, so that for all quants that he can make, there is a quantum that I can make, so that for all quants that he can make, I have a quantum, so that he does not have any more quants.
In this way we get the sum of the quants without actually writing down all the quants. You have this nice theoretical game mix.
So, that is the first thing. If the duplicator wins, then the quants up to the quants are indistinguishable. And if the signature is finally there,
then the inversion is also valid. That means, whenever two structures are indistinguishable up to the quantum rank M, the game is won by the duplicator.
So, we can now create the trivial direction in 15 minutes. It will be tight. Let's see.
So, we will first create the light direction, the direction of the so-called semantic invariance, because this is the logical invariance, which is usually light.
So, we induce via phi with the appropriate maximum quantum rank.
So, let's make the first case. Phi could be an atomic formula. There are two types of atomic formulas, because there are no function symbols.
So, we use the appropriate variables, which are all called Xi. So, phi can be one of two things. As an atomic formula, it can be an equation between two variables, which then have to be called Xi and Xj.
Or, phi is an atomic predicate application of a k-digit predicate P on some k variables Xi1 to Xik.
So, this is the definition of partial iso.
So, on the left side, on the A side, there is an equation Xi equal to Xj, which is fulfilled when the i-th value in the vector is equal to the j-th value in the vector, because these are the interpretations of Xi and Xj.
So, the condition 1 tells me that the left side is the case when the right side is the case.
So, as soon as I have a partial iso, it works for atomic phi. Why do I have a partial iso? Because duplicator wins.
And this is why a partial iso must be prepared, at least in the zero round, otherwise it can also be that there was no partial iso at the end and then spoiler wins.
So, that was easy. And we can continue here.
So.
So, there are two induction steps for the bullish cases.
So, I can apply and and negation. And as usual, they are trivial.
So, when the fill-in is, for example, of phi equivalent on both sides, then the fill-in is also of non-phi equivalent on both sides.
So, either they fill in both phi, then they both do not fill in phi, or they both do not fill in phi, then they both fill in phi.
So, that's very easy and just like here for and, that's the case in almost all such cases.
The only interesting case is the quantum of existence. So, exists X phi.
So, let's start on the left.
So, let's assume that the quantum of existence is fulfilled. So, what does that mean?
I have lost a little bit here. That's because I have locked in a term here.
So, I have to... no, wait a minute. Do I have to do that at all?
Oh no, I don't have to do that. I don't have to do that. All right, everything was right. That's the other way around.
So, we already know that the duplicator wins. I wanted to say, I forgot to give the strategy, but that comes first in the other direction.
So, again. So, here the case exists X phi. So, again.
Presenters
Zugänglich über
Offener Zugang
Dauer
00:23:43 Min
Aufnahmedatum
2018-04-30
Hochgeladen am
2019-04-28 21:39:02
Sprache
de-DE
- Algorithmen für Aussagenlogik
-
Tableaukalküle
-
Anfänge der (endlichen) Modelltheorie
-
Modal- und Beschreibungslogiken
-
Ontologieentwurf
Lernziele und Kompetenzen:
Fachkompetenz Wissen Die Studierenden geben Definitionen der Syntax und Semantik verschiedener WIssensrepräsentationssprachen wieder und legen wesentliche Eigenschaften hinsichtlich Entscheidbarkeit, Komplexität und Ausdrucksstärke dar. Anwenden Die Studierenden wenden Deduktionsalgorithmen auf Beispielformeln an. Sie stellen einfache Ontologien auf und führen anhand der diskutierten Techniken Beweise elementarer logischer Metaeigenschaften. Analysieren Die Studierenden klassifizieren Logiken nach grundlegenden Eigenschaften wie Ausdrucksstärke und Komplexität. Sie wählen für ein gegebenes Anwendungsproblem geeignete Formalismen aus. Lern- bzw. Methodenkompetenz Die Studierenden erarbeiten selbständig formale Beweise. Sozialkompetenz Die Studierenden arbeiten in Kleingruppen erfolgreich zusammen.
Literatur:
- M Krötzsch, F Simancik, I Horrocks; A description logic primer, arXiv, 2012
-
F. Baader et al. (ed.): The Description Logic Handbook, Cambridge University Press, 2003
-
M. Huth, M. Ryan: Logic in Computer Science, Cambridge University Press, 2004
-
L. Libkin: Elements of Finite Model Theory, Springer, 2004